#include <iostream>
#include <unordered_map>  // 竞赛最常用的哈希表
#include <unordered_set>  // 竞赛最常用的哈希集合
#include <map>            // 红黑树，有序
#include <set>            // 红黑树集合，有序
#include <list>           // 双向链表
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 使用STL unordered_map
void unorderedMapDemo() {
    cout << "=== STL unordered_map演示 ===" << endl;
    
    unordered_map<string, int> ageMap;
    
    // 插入元素
    cout << "插入元素:" << endl;
    ageMap["Alice"] = 25;
    cout << "Alice: 25" << endl;
    ageMap["Bob"] = 30;
    cout << "Bob: 30" << endl;
    ageMap.insert({"Charlie", 35});
    cout << "Charlie: 35" << endl;
    
    // 访问元素
    cout << "\n访问元素:" << endl;
    cout << "Alice的年龄: " << ageMap["Alice"] << endl;
    cout << "Bob的年龄: " << ageMap["Bob"] << endl;
    
    // 检查键是否存在
    cout << "\n检查键是否存在:" << endl;
    if(ageMap.find("David") == ageMap.end()) {
        cout << "David不存在" << endl;
    } else {
        cout << "David的年龄: " << ageMap["David"] << endl;
    }
    
    // 遍历哈希表
    cout << "\n遍历哈希表:" << endl;
    for(const auto& pair : ageMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    // 删除元素
    cout << "\n删除Bob:" << endl;
    ageMap.erase("Bob");
    cout << "删除Bob后大小: " << ageMap.size() << endl;
    
    // 再次遍历
    cout << "剩余元素:" << endl;
    for(const auto& pair : ageMap) {
        cout << pair.first << ": " << pair.second << endl;
    }
}

// 使用STL unordered_set
void unorderedSetDemo() {
    cout << "\n=== STL unordered_set演示 ===" << endl;
    
    unordered_set<int> numberSet;
    
    // 插入元素
    cout << "插入元素: 1, 2, 3, 2 (注意2重复)" << endl;
    numberSet.insert(1);
    numberSet.insert(2);
    numberSet.insert(3);
    numberSet.insert(2); // 重复元素不会被插入
    
    // 检查元素是否存在
    cout << "\n检查元素是否存在:" << endl;
    if(numberSet.find(2) != numberSet.end()) {
        cout << "2存在于集合中" << endl;
    }
    if(numberSet.find(4) == numberSet.end()) {
        cout << "4不存在于集合中" << endl;
    }
    
    // 遍历集合
    cout << "\n集合内容: ";
    for(const auto& num : numberSet) {
        cout << num << " ";
    }
    cout << endl;
    cout << "集合大小: " << numberSet.size() << endl;
    
    // 删除元素
    cout << "\n删除元素2:" << endl;
    numberSet.erase(2);
    cout << "删除2后大小: " << numberSet.size() << endl;
    cout << "剩余元素: ";
    for(const auto& num : numberSet) {
        cout << num << " ";
    }
    cout << endl;
}

// 自定义简单哈希表实现
class SimpleHashTable {
private:
    static const int TABLE_SIZE = 10;
    pair<string, int> table[TABLE_SIZE];
    bool occupied[TABLE_SIZE] = {false};
    
    // 简单哈希函数
    int hashFunction(const string& key) {
        int hash = 0;
        for(char c : key) {
            hash += c;
        }
        return hash % TABLE_SIZE;
    }

public:
    void insert(const string& key, int value) {
        int index = hashFunction(key);
        cout << "键 '" << key << "' 的哈希值: " << index << endl;
        
        // 线性探测解决冲突
        int originalIndex = index;
        while(occupied[index]) {
            if(table[index].first == key) {
                // 键已存在，更新值
                cout << "键 '" << key << "' 已存在，更新值从 " << table[index].second << " 到 " << value << endl;
                table[index].second = value;
                return;
            }
            cout << "位置 " << index << " 被占用，探测下一个位置" << endl;
            index = (index + 1) % TABLE_SIZE;
            if(index == originalIndex) {
                cout << "哈希表已满!" << endl;
                return;
            }
        }
        
        table[index] = {key, value};
        occupied[index] = true;
        cout << "在位置 " << index << " 插入键值对: " << key << " -> " << value << endl;
    }
    
    int get(const string& key) {
        int index = hashFunction(key);
        int originalIndex = index;
        
        while(occupied[index]) {
            if(table[index].first == key) {
                cout << "找到键 '" << key << "' 在位置 " << index << "，值为 " << table[index].second << endl;
                return table[index].second;
            }
            index = (index + 1) % TABLE_SIZE;
            if(index == originalIndex) {
                break;
            }
        }
        
        cout << "键不存在: " << key << endl;
        return -1;
    }
    
    void remove(const string& key) {
        int index = hashFunction(key);
        int originalIndex = index;
        
        while(occupied[index]) {
            if(table[index].first == key) {
                occupied[index] = false;
                cout << "删除键 '" << key << "' (位置 " << index << ")" << endl;
                return;
            }
            index = (index + 1) % TABLE_SIZE;
            if(index == originalIndex) {
                break;
            }
        }
        
        cout << "要删除的键不存在: " << key << endl;
    }
    
    void display() {
        cout << "哈希表内容:" << endl;
        for(int i = 0; i < TABLE_SIZE; i++) {
            if(occupied[i]) {
                cout << "位置 " << i << ": " << table[i].first << " -> " << table[i].second << endl;
            } else {
                cout << "位置 " << i << ": 空" << endl;
            }
        }
    }
};

void customHashTableDemo() {
    cout << "\n=== 自定义哈希表演示 ===" << endl;
    
    SimpleHashTable ht;
    
    cout << "插入操作:" << endl;
    ht.insert("apple", 5);
    ht.insert("banana", 3);
    ht.insert("orange", 7);
    ht.insert("grape", 2);
    
    cout << "\n当前哈希表状态:" << endl;
    ht.display();
    
    cout << "\n查找操作:" << endl;
    cout << "apple的数量: " << ht.get("apple") << endl;
    cout << "banana的数量: " << ht.get("banana") << endl;
    cout << "cherry的数量: " << ht.get("cherry") << endl;
    
    cout << "\n删除操作:" << endl;
    ht.remove("banana");
    cout << "删除后查找banana: " << ht.get("banana") << endl;
    
    cout << "\n最终哈希表状态:" << endl;
    ht.display();
}

// 哈希表的应用：词频统计
void wordFrequencyDemo() {
    cout << "\n=== 词频统计演示 ===" << endl;
    
    string text = "hello world hello cpp world cpp hello";
    cout << "文本: \"" << text << "\"" << endl;
    
    unordered_map<string, int> wordCount;
    
    // 简单的分词（按空格分割）
    string word = "";
    for(char c : text) {
        if(c == ' ') {
            if(!word.empty()) {
                wordCount[word]++;
                cout << "处理单词: " << word << endl;
                word = "";
            }
        } else {
            word += c;
        }
    }
    if(!word.empty()) {
        wordCount[word]++;
        cout << "处理单词: " << word << endl;
    }
    
    cout << "\n词频统计结果:" << endl;
    for(const auto& pair : wordCount) {
        cout << pair.first << ": " << pair.second << " 次" << endl;
    }
}

// 哈希表的应用：两数之和问题
vector<int> twoSum(vector<int>& nums, int target) {
    cout << "\n=== 两数之和问题演示 ===" << endl;
    cout << "数组: ";
    for(int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if(i < nums.size() - 1) cout << ", ";
    }
    cout << endl;
    cout << "目标值: " << target << endl;
    
    unordered_map<int, int> numMap;
    
    for(int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        cout << "检查数字 " << nums[i] << "，寻找补数 " << complement << endl;
        
        if(numMap.find(complement) != numMap.end()) {
            cout << "找到补数 " << complement << " 在索引 " << numMap[complement] << endl;
            cout << "结果: [" << numMap[complement] << ", " << i << "]" << endl;
            return {numMap[complement], i};
        }
        
        numMap[nums[i]] = i;
        cout << "将 " << nums[i] << " 及其索引 " << i << " 存入哈希表" << endl;
    }
    
    cout << "未找到解" << endl;
    return {};
}

// 哈希表的应用：去重
void removeDuplicatesDemo() {
    cout << "\n=== 数组去重演示 ===" << endl;
    
    vector<int> nums = {1, 2, 2, 3, 4, 4, 5, 1, 6};
    cout << "原数组: ";
    for(int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    unordered_set<int> seen;
    vector<int> result;
    
    for(int num : nums) {
        if(seen.find(num) == seen.end()) {
            seen.insert(num);
            result.push_back(num);
            cout << "添加 " << num << " 到结果" << endl;
        } else {
            cout << "跳过重复元素 " << num << endl;
        }
    }
    
    cout << "去重后数组: ";
    for(int num : result) {
        cout << num << " ";
    }
    cout << endl;
}

// ================ 竞赛常用写法 ================

// 竞赛推荐：unordered_map简洁写法
void unorderedMapContestDemo() {
    cout << "\n=== 竞赛常用：unordered_map演示 ===" << endl;
    
    unordered_map<string, int> mp;
    
    // 简洁的插入和访问
    mp["apple"] = 5;
    mp["banana"] = 3;
    mp["orange"] = 7;
    
    // 检查存在性
    if(mp.count("apple")) {
        cout << "apple存在，值为: " << mp["apple"] << endl;
    }
    
    // 遍历（竞赛常用）
    for(auto& [key, value] : mp) {  // C++17结构化绑定
        cout << key << ": " << value << endl;
    }
    
    // 删除
    mp.erase("banana");
    cout << "删除banana后大小: " << mp.size() << endl;
}

// 竞赛常用：unordered_set去重
void unorderedSetContestDemo() {
    cout << "\n=== 竞赛常用：unordered_set演示 ===" << endl;
    
    vector<int> nums = {1, 2, 2, 3, 3, 3, 4, 4, 5};
    
    // 去重
    unordered_set<int> uniqueNums(nums.begin(), nums.end());
    
    cout << "原数组: ";
    for(int x : nums) cout << x << " ";
    cout << endl;
    
    cout << "去重后: ";
    for(int x : uniqueNums) cout << x << " ";
    cout << endl;
    
    // 快速查找
    cout << "查找结果:" << endl;
    for(int target : {2, 6, 3}) {
        if(uniqueNums.count(target)) {
            cout << target << " 存在" << endl;
        } else {
            cout << target << " 不存在" << endl;
        }
    }
}

// 竞赛常见：两数之和问题
vector<int> twoSumContest(const vector<int>& nums, int target) {
    unordered_map<int, int> mp;  // 值 -> 索引
    
    for(int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if(mp.count(complement)) {
            return {mp[complement], i};
        }
        mp[nums[i]] = i;
    }
    
    return {};
}

// 竞赛常见：字符频率统计
void charFrequencyDemo() {
    cout << "\n=== 竞赛常见：字符频率统计 ===" << endl;
    
    string s = "hello world";
    unordered_map<char, int> freq;
    
    for(char c : s) {
        freq[c]++;
    }
    
    cout << "字符串: \"" << s << "\"" << endl;
    cout << "字符频率:" << endl;
    for(auto& [ch, count] : freq) {
        if(ch != ' ') {  // 忽略空格
            cout << "'" << ch << "': " << count << endl;
        }
    }
}

// 竞赛技巧：数组代替map
void arrayInsteadOfMapDemo() {
    cout << "\n=== 竞赛技巧：数组代替map ===" << endl;
    
    // 当键范围较小时，用数组更高效
    vector<int> cnt(26, 0);  // 26个字母的计数
    
    string s = "programming";
    for(char c : s) {
        cnt[c - 'a']++;  // 假设只有小写字母
    }
    
    cout << "字符串: \"" << s << "\"" << endl;
    cout << "字母频率:" << endl;
    for(int i = 0; i < 26; i++) {
        if(cnt[i] > 0) {
            cout << "'" << char('a' + i) << "': " << cnt[i] << endl;
        }
    }
}

// 竞赛常见：LRU Cache实现
class LRUCacheContest {
private:
    int capacity;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
    list<pair<int, int>> cacheList;

public:
    LRUCacheContest(int cap) : capacity(cap) {}
    
    int get(int key) {
        auto it = cacheMap.find(key);
        if(it == cacheMap.end()) return -1;
        
        // 移动到头部
        cacheList.splice(cacheList.begin(), cacheList, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = cacheMap.find(key);
        if(it != cacheMap.end()) {
            it->second->second = value;
            cacheList.splice(cacheList.begin(), cacheList, it->second);
            return;
        }
        
        if(cacheMap.size() >= capacity) {
            int lruKey = cacheList.back().first;
            cacheMap.erase(lruKey);
            cacheList.pop_back();
        }
        
        cacheList.emplace_front(key, value);
        cacheMap[key] = cacheList.begin();
    }
};

int main() {
    // 传统哈希表演示
    unorderedMapDemo();
    unorderedSetDemo();
    customHashTableDemo();
    wordFrequencyDemo();
    
    // 竞赛常用写法
    unorderedMapContestDemo();
    unorderedSetContestDemo();
    charFrequencyDemo();
    arrayInsteadOfMapDemo();
    
    // 竞赛常见应用
    cout << "\n=== 竞赛常见应用 ===" << endl;
    
    // 两数之和
    vector<int> nums = {2, 7, 11, 15};
    vector<int> result = twoSumContest(nums, 9);
    cout << "两数之和结果: [" << result[0] << ", " << result[1] << "]" << endl;
    
    // 传统两数之和演示
    twoSum(nums, 9);
    
    // LRU Cache
    LRUCacheContest lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    cout << "LRU get(1): " << lru.get(1) << endl;
    lru.put(3, 3);
    cout << "LRU get(2): " << lru.get(2) << endl;
    
    // 数组去重
    removeDuplicatesDemo();
    
    cout << "\n=== 竞赛选择指南 ===" << endl;
    cout << "1. 键值存储：使用 unordered_map<K,V>" << endl;
    cout << "2. 集合去重：使用 unordered_set<T>" << endl;
    cout << "3. 需要排序：使用 map<K,V> / set<T>" << endl;
    cout << "4. 计数统计：当范围小时用数组代替map" << endl;
    cout << "5. 字符处理：用数组[26]代替map<char,int>" << endl;
    
    cout << "\n=== 哈希冲突解决方法 ===" << endl;
    cout << "1. 链地址法：每个桶使用链表存储冲突元素" << endl;
    cout << "2. 开放地址法：" << endl;
    cout << "   - 线性探测" << endl;
    cout << "   - 二次探测" << endl;
    cout << "   - 双重哈希" << endl;
    
    cout << "\n=== 时间复杂度（平均情况）===" << endl;
    cout << "插入: O(1)" << endl;
    cout << "删除: O(1)" << endl;
    cout << "查找: O(1)" << endl;
    
    cout << "\n=== 哈希表的应用场景 ===" << endl;
    cout << "1. 字典实现" << endl;
    cout << "2. 缓存系统" << endl;
    cout << "3. 数据库索引" << endl;
    cout << "4. 词频统计" << endl;
    cout << "5. 去重操作" << endl;
    cout << "6. 快速查找" << endl;
    
    return 0;
}
